package graph;

import java.util.Vector;

/**
 * 
 * O(v+e) Strongly connected components tarjan solution, tested
 * 
 * @author yinzichen
 * 
 */
public class TarjanSCC {

	Vector<Vector<Integer>> adj;
	int[] used;
	int[] low;
	int[] num;
	int[] stack;
	int[] u;
	int id, top;

	public int[] tarjan(Vector<Vector<Integer>> directedGraph) {
		int n = directedGraph.size();
		adj = directedGraph;
		used = new int[n];
		low = new int[n];
		num = new int[n];
		stack = new int[n];
		id = 0;
		top = -1;
		for (int i = 0; i < n; ++i) {
			if (used[i] == 0) {
				dfs(i);
			}
		}
		return low;
	}

	private int dfs(int u) {
		num[u] = id;
		low[u] = id++;
		used[u] = 1;
		stack[++top] = u;
		for (int v : adj.get(u)) {
			if (used[v] == 0) {
				low[u] = Math.min(low[u], dfs(v));
			} else if (used[v] == 1) {
				low[u] = Math.min(low[u], num[v]);
			}
		}
		if (low[u] == num[u]) {
			int v = 0;
			do {
				v = stack[top--];
				low[v] = num[u];
				used[v] = 2;
			} while (u != v);
		}
		return low[u];
	}

	public Vector<Vector<Integer>> getDAG(Vector<Vector<Integer>> g) {
		tarjan(g);
		int n = g.size();
		int cnt = 0;
		u = new int[n];
		for (int i = 0; i < n; ++i) {
			if (low[i] == num[i]) {
				u[num[i]] = cnt++;
			}
		}
		Vector<Vector<Integer>> dag = new Vector<Vector<Integer>>();
		for (int i = 0; i < cnt; ++i)
			dag.add(new Vector<Integer>());
		for (int i = 0; i < n; ++i) {
			for (int idx : g.get(i)) {
				int a = low[i], b = low[idx];
				if (a != b) {
					dag.get(u[a]).add(u[b]);
				}
			}
		}
		return dag;
	}

}
